package com.zjsru.plan2024.oneday;

/**
 * 377. 组合总和 Ⅳ
 * @Author: cookLee
 * @Date: 2024-04-22
 */
public class CombinationSum4 {

    /**
     * 主
     * \
     * 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
     * \
     * 输入：nums = [1,2,3], target = 4
     * 输出：7
     * 解释：
     * 所有可能的组合为：
     * (1, 1, 1, 1)
     * (1, 1, 2)
     * (1, 2, 1)
     * (1, 3)
     * (2, 1, 1)
     * (2, 2)
     * (3, 1)
     * 请注意，顺序不同的序列被视作不同的组合。
     * \
     * 输入：nums = [9], target = 3
     * 输出：0
     * \
     * @param args args
     */
    public static void main(String[] args) {
        CombinationSum4 combinationSum4 = new CombinationSum4();
        int[] nums = new int[]{1, 2, 3};
        int target = 4;
        System.out.println(combinationSum4.combinationSum4(nums, target));
    }

    /**
     * 组合sum4:动态规划
     *
     * @param nums   nums
     * @param target 目标
     * @return int
     */
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        //计算每轮目标值i的组合法
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if(num <= i){
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

}
